package fun.coding.leetcode;

public class IntegerToRoman {

	public static void main(String[] args) {

	}
	
	 /*
     * stupid questin, only a few combinations:http://en.wikipedia.org/wiki/Roman_numerals
     */
	public String intToRoman(int num) {
        String[] roman = {"M", "CM", "D",   "CD",   "C",  "XC", "L",  "XL", "X", "IX", "V", "IV", "I"};
        int[] value  = {1000,  900,  500,    400,   100,  90,   50,   40,   10,    9,   5,    4,  1};
        
        StringBuilder sb = new StringBuilder();
        
        while (num > 0) {
            for (int i = 0; i < value.length; ++i) {
                int quote = num / value[i];
                while (quote > 0) {
                    sb.append(roman[i]);
                    quote--;
                }
                // Note, this is a better way to calculate the remainder, 140 / 100 = 4, 140 % 100 = 40, 140 % 1000 = 140, 
                // rather than 140 - 1*100 = 40
                num %= value[i];
            }
        }
        
        return sb.toString();
    }
}
